package com.leetcode.algorithm.y21.m07;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * leetcode-cn.com
 * 滑动窗口
 * 
 * @author jie.deng
 *
 */
public class MySolution0729 {
	
	/**
	 * 1052. 爱生气的书店老板
	 * 
     * 今天，书店老板有一家店打算试营业 customers.length 分钟。每分钟都有一些顾客（customers[i]）会进入书店，所有这些顾客都会在那一分钟结束后离开。
     * 
     * 在某些时候，书店老板会生气。 如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。 当书店老板生气时，那一分钟的顾客就会不满意，不生气则他们是满意的。
     * 
     * 书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 X 分钟不生气，但却只能使用一次。
     * 
     * 请你返回这一天营业下来，最多有多少客户能够感到满意。
     *  
     * 
     * 示例：
     * 
     * 输入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
     * 输出：16
     * 解释：
     * 书店老板在最后 3 分钟保持冷静。
     * 感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.
     *  
     * 
     * 提示：
     * 
     * 1 <= X <= customers.length == grumpy.length <= 20000
     * 0 <= customers[i] <= 1000
     * 0 <= grumpy[i] <= 1
     * 
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/grumpy-bookstore-owner
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
	 * 
	 * @param customers
	 * @param grumpy
	 * @param minutes
	 * @return
	 */
	public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
		// maxSatisfiedCnt表示生气时抑制情绪满意的顾客的最大人数
		int maxSatisfiedCnt = 0;
		// satisfiedCnt表示生气时抑制情绪滑动窗口内客户数
		int satisfiedCnt = 0;
		// satisfiedCnt表示生气时抑制情绪滑动窗口内客户数
		LinkedList<Integer> grumpy1IdxQueue = new LinkedList<Integer>();
		int grumpy0Cnt = 0;

		for (int i = 0; i < grumpy.length; i++) {
			if (grumpy[i] == 0) {
				// 不生气可以获得客户的满意
				grumpy0Cnt += customers[i];
				continue;
			}

			// 生气
			grumpy1IdxQueue.offer(Integer.valueOf(i));
			while (!grumpy1IdxQueue.isEmpty() && i - grumpy1IdxQueue.peek().intValue() + 1 > minutes) {
				int grumpyIdx = grumpy1IdxQueue.poll().intValue();
				satisfiedCnt -= customers[grumpyIdx];
			}
			satisfiedCnt += customers[i];
			maxSatisfiedCnt = Math.max(maxSatisfiedCnt, satisfiedCnt);
		}

		return maxSatisfiedCnt + grumpy0Cnt;
	}
    
    /**
     * 1208. 尽可能使字符串相等
     * 
     * 给你两个长度相同的字符串，s 和 t。
     * 
     * 将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销（开销可能为 0），也就是两个字符的 ASCII 码值的差的绝对值。
     * 
     * 用于变更字符串的最大预算是 maxCost。在转化字符串时，总开销应当小于等于该预算，这也意味着字符串的转化可能是不完全的。
     * 
     * 如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串，则返回可以转化的最大长度。
     * 
     * 如果 s 中没有子字符串可以转化成 t 中对应的子字符串，则返回 0。
     * 
     *  
     * 
     * 示例 1：
     * 
     * 输入：s = "abcd", t = "bcdf", maxCost = 3
     * 输出：3
     * 解释：s 中的 "abc" 可以变为 "bcd"。开销为 3，所以最大长度为 3。
     * 示例 2：
     * 
     * 输入：s = "abcd", t = "cdef", maxCost = 3
     * 输出：1
     * 解释：s 中的任一字符要想变成 t 中对应的字符，其开销都是 2。因此，最大长度为 1。
     * 示例 3：
     * 
     * 输入：s = "abcd", t = "acde", maxCost = 0
     * 输出：1
     * 解释：a -> a, cost = 0，字符串未发生变化，所以最大长度为 1。
     *  
     * 
     * 提示：
     * 
     * 1 <= s.length, t.length <= 10^5
     * 0 <= maxCost <= 10^6
     * s 和 t 都只含小写英文字母。
     * 
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/get-equal-substrings-within-budget
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * 
     * @param s
     * @param t
     * @param maxCost
     * @return
     */
	public int equalSubstring(String s, String t, int maxCost) {
		int maxLen = 0;
		int cost = 0;
		int[] diffArr = new int[s.length()];
		int left = 0;
		for (int right = 0; right < s.length(); right++) {
			diffArr[right] = Math.abs(s.charAt(right) - t.charAt(right));
			cost += diffArr[right];

			while (cost > maxCost) {
				cost -= diffArr[left];
				left++;
			}

			maxLen = Math.max(maxLen, right - left + 1);
		}

		return maxLen;
	}
    
    /**
     * 1423. 可获得的最大点数
     * 
     * 几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。
     * 
     * 每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。
     * 
     * 你的点数就是你拿到手中的所有卡牌的点数之和。
     * 
     * 给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。
     * 
     *  
     * 
     * 示例 1：
     * 
     * 输入：cardPoints = [1,2,3,4,5,6,1], k = 3
     * 输出：12
     * 解释：第一次行动，不管拿哪张牌，你的点数总是 1 。但是，先拿最右边的卡牌将会最大化你的可获得点数。最优策略是拿右边的三张牌，最终点数为 1 + 6 + 5 = 12 。
     * 示例 2：
     * 
     * 输入：cardPoints = [2,2,2], k = 2
     * 输出：4
     * 解释：无论你拿起哪两张卡牌，可获得的点数总是 4 。
     * 示例 3：
     * 
     * 输入：cardPoints = [9,7,7,9,7,7,9], k = 7
     * 输出：55
     * 解释：你必须拿起所有卡牌，可以获得的点数为所有卡牌的点数之和。
     * 示例 4：
     * 
     * 输入：cardPoints = [1,1000,1], k = 1
     * 输出：1
     * 解释：你无法拿到中间那张卡牌，所以可以获得的最大点数为 1 。 
     * 示例 5：
     * 
     * 输入：cardPoints = [1,79,80,1,1,1,200,1], k = 3
     * 输出：202
     *  
     * 
     * 提示：
     * 
     * 1 <= cardPoints.length <= 10^5
     * 1 <= cardPoints[i] <= 10^4
     * 1 <= k <= cardPoints.length
     * 
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/maximum-points-you-can-obtain-from-cards
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * 
     * @param cardPoints
     * @param k
     * @return
     */
	public int maxScore(int[] cardPoints, int k) {
		int allSum = 0;
		int len = cardPoints.length;
		for (int i = 0; i < len; i++) {
			allSum += cardPoints[i];
		}

		int minSum = 0;
		int sum = 0;
		int cnt = len - k;

		for (int i = 0; i < cnt; i++) {
			sum += cardPoints[i];
		}
		minSum = sum;
		for (int i = cnt; i < len; i++) {
			sum -= cardPoints[i - cnt];
			sum += cardPoints[i];
			minSum = Math.min(minSum, sum);
		}

		return allSum - minSum;
	}
    
    /**
     * 1695. 删除子数组的最大得分
     * 
     * 给你一个正整数数组 nums ，请你从中删除一个含有 若干不同元素 的子数组。删除子数组的 得分 就是子数组各元素之 和 。
     * 
     * 返回 只删除一个 子数组可获得的 最大得分 。
     * 
     * 如果数组 b 是数组 a 的一个连续子序列，即如果它等于 a[l],a[l+1],...,a[r] ，那么它就是 a 的一个子数组。
     * 
     *  
     * 
     * 示例 1：
     * 
     * 输入：nums = [4,2,4,5,6]
     * 输出：17
     * 解释：最优子数组是 [2,4,5,6]
     * 示例 2：
     * 
     * 输入：nums = [5,2,1,2,5,2,1,2,5]
     * 输出：8
     * 解释：最优子数组是 [5,2,1] 或 [1,2,5]
     *  
     * 
     * 提示：
     * 
     * 1 <= nums.length <= 105
     * 1 <= nums[i] <= 104
     * 
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/maximum-erasure-value
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * 
     * @param nums
     * @return
     */
	public int maximumUniqueSubarray(int[] nums) {
		Map<Integer, Integer> idxMap = new HashMap<>();
		int maxSum = 0;
		int sum = 0;
		int left = 0;
		for (int right = 0; right < nums.length; right++) {
			Integer cur = Integer.valueOf(nums[right]);
			if (idxMap.containsKey(cur)) {
				int idx = idxMap.get(nums[right]).intValue();
				while (left <= idx) {
					sum -= nums[left];
					left++;
				}
			}
			idxMap.put(cur, right);
			sum += nums[right];
			maxSum = Math.max(maxSum, sum);
		}

		return maxSum;
	}
    
    
    /**
     * 424. 替换后的最长重复字符
     * 
     * 给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。
     * 
     * 注意：字符串长度 和 k 不会超过 104。
     * 
     *  
     * 
     * 示例 1：
     * 
     * 输入：s = "ABAB", k = 2
     * 输出：4
     * 解释：用两个'A'替换为两个'B',反之亦然。
     * 示例 2：
     * 
     * 输入：s = "AABABBA", k = 1
     * 输出：4
     * 解释：
     * 将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
     * 子串 "BBBB" 有最长重复字母, 答案为 4。
     * 
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/longest-repeating-character-replacement
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * 
     * @param s
     * @param k
     * @return
     */
    public int characterReplacement(String s, int k) {
		return k;
    }
}
